package BinaryTree;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 周斌
 * Date: 2024-03-17
 * Time: 16:14
 */
public class BinaryTree {
    static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;


        public TreeNode(int val) {
            this.val = val;
        }
    }

    public TreeNode careTree1() {
        TreeNode A = new TreeNode(10);
        TreeNode B = new TreeNode(6);
        TreeNode C = new TreeNode(4);
        TreeNode D = new TreeNode(8);
        TreeNode E = new TreeNode(14);
        TreeNode F = new TreeNode(12);
        TreeNode G = new TreeNode(16);

        A.left = B;
        A.right = E;

        B.left = C;
        B.right = D;

        E.left = F;
        E.right = G;

        return A;
    }

    public int i = 0;

    public TreeNode careTree2(String str) {
        //创建一个结点
        TreeNode root = null;
        //遍历str字符串
        char ch = str.charAt(i);
        if (ch != '#') {
            root = new TreeNode(ch);
            i++;
            root.left = careTree2(str);
            root.right = careTree2(str);
        } else {
            i++;
        }
        return root;
    }


    //通过前序遍历和中序遍历创建二叉树
    /*public  int preIndex ;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder,inorder,0,inorder.length-1);
    }
    private TreeNode buildTreeChild(int[] preorder,int[] inorder,int begin,int end) {
        //出递归的条件
        if(begin > end) {
            return null;
        }
        //创建结点(根结点)
        TreeNode root = new TreeNode(preorder[preIndex]);
        //在中序遍历中找到preindex的这个根结点
        int rootIndex = findIndex(inorder,begin,end,preorder[preIndex]);
        //遍历先序数组加1
        preIndex++;
        //创建左树
        root.left = buildTreeChild(preorder,inorder,begin,rootIndex-1);
        //创建左树
        root.right = buildTreeChild(preorder,inorder,rootIndex+1,end);
        return root;
    }
    private int findIndex(int[] inorder,int begin,int end ,int key) {
        for(int i=begin;i<=end;i++) {
            if(inorder[i] == key) {
                return i;
            }
        }
        return  -1;
    }*/


    //通过中序遍历和后序遍历创建二叉树
    /*public int postIndex;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postIndex = postorder.length-1;
        return buildTreeChild(postorder,inorder,0,inorder.length-1);
    }
    private TreeNode buildTreeChild(int[] postorder,int[] inorder,int begin,int end) {
        //出递归的条件
        if(begin > end) {
            return null;
        }
        //创建结点(根结点)
        TreeNode root = new TreeNode(postorder[postIndex]);
        //在中序遍历中找到preindex的这个根结点
        int rootIndex = findIndex(inorder,begin,end,postorder[postIndex]);
        //遍历后序数组减1
        postIndex--;
        //创建右树
        root.right = buildTreeChild(postorder,inorder,rootIndex+1,end);
        //创建左树
        root.left = buildTreeChild(postorder,inorder,begin,rootIndex-1);
        return root;
    }
    private int findIndex(int[] inorder,int begin,int end ,int key) {
        for(int i=begin;i<=end;i++) {
            if(inorder[i] == key) {
                return i;
            }
        }
        return  -1;
    }
*/
    // 前序遍历 根 左 右
    public void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    // 中序遍历 左 根 右
    public void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    // 后序遍历 左 右 根
    public void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }

    // 获取树中节点的个数
    int size(TreeNode root) {
        //子问题：左树结点的个数+右树结点的个数+根的个树
        if (root == null) {
            return 0;
        }
        return size(root.left) + size(root.right) + 1;
    }

    // 获取叶子节点的个数
    int getLeafNodeCount(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //判断是否为叶子结点
        if (root.left == null && root.right == null) {
            return 1;
        }
        return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
    }

    // 获取第K层节点的个数
    int getKLevelNodeCount(TreeNode root, int k) {
        if (root == null) {
            return 0;
        }
        //k==1时返回1
        if (k == 1) {
            return 1;
        }
        //遍历左子树和右子树
        return getKLevelNodeCount(root.left, k - 1) + getKLevelNodeCount(root.right, k - 1);
    }

    // 获取二叉树的高度
    int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //比较左子树与右子树的最大值然后加1
        int getLeftMax = getHeight(root.left);
        int getRightMax = getHeight(root.right);

        return Math.max(getLeftMax, getRightMax) + 1;
    }

    int getHeight1(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //比较左子树与右子树的最大值然后加1
        return Math.max(getHeight1(root.left), getHeight1(root.right)) + 1;
    }

    // 检测值为value的元素是否存在
    TreeNode find(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        //判断根结点是否为检测值
        if (root.val == val) {
            return root;
        }
        //然后遍历左子树，判断有没有和val值相同的，有则返回，没有则遍历右子树
        TreeNode leftVal = find(root.left, val);
        if (leftVal != null) {
            return leftVal;
        }
        //然后遍历右子树，判断有没有和val值相同的，有则返回
        TreeNode rightVal = find(root.right, val);
        if (rightVal != null) {
            return rightVal;
        }
        //说明左子树找不到右子树也找不到，最后返回null
        return null;
    }

    //层序遍历
    public void levelOrder(TreeNode root) {
        //1.判断根结点是否为空
        if (root == null) {
            return;
        }
        //2.不空，则将根结点放入队中
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            //3.出队
            TreeNode cur = queue.poll();
            //打印cur
            System.out.print(cur.val + " ");
            //4.判断cur的左边和右边是否为null
            //左边
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            //右边
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }
    //以二维数组的形式存储一层一层的元素
   /* public List<List<Integer>> levelOrder1(TreeNode root) {
        // 定义一个二维数组
        List<List<Integer>> retList = new ArrayList<>();
        // 1.root为空
        if (root == null) {
            return retList;
        }
        // 2.root不为空，将根结点入队
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        // 3.出循环条件为队中为空
        while (!queue.isEmpty()) {
            // 记录队中有多少元素
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            while (size != 0) {
                TreeNode cur = queue.poll();
                list.add(cur.val);
                size--;
                // 判断入队前是否为null
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            retList.add(list);
        }
        return retList;
    }*/

    // 判断一棵树是不是完全二叉树
    public boolean isCompleteTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur != null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            } else {
                break;//判断队中剩下的元素是不是null
            }
        }
        //判断队中剩下的元素是不是全为null，如果直接用队中是否为空来判断是不适宜的，因为null在队中也算元素个数，
        // 只能去遍历这个队中剩下的元素是不是都为null
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur != null) {
                return false;
            }
        }
        return true;
    }

    //判断相同的树
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //1.结构上

        //1.1 一个根结点为空，另一个不为空
        if (p == null && q != null || p != null && q == null) {
            return false;
        }
        //1.2 两个根结点都为空
        if (p == null && q == null) {
            return true;
        }
        //2.根的值不相同
        if (p.val != q.val) {
            return false;
        }
        //到了这里说明根结点相同并且也相同
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    //另一棵树的子树
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) {
            return false;
        }
        if (isSameTree(root, subRoot)) {
            return true;
        }
        if (isSubtree(root.left, subRoot)) {
            return true;
        }
        if (isSubtree(root.right, subRoot)) {
            return true;
        }
        return false;
    }

    //翻转二叉树
    public TreeNode invertTree(TreeNode root) {
        //1.判断根结点
        if (root == null) {
            return null;
        }

        //加一个判断根结点的左右结点是null则直接返回根结点root ，可以减少很多的左右树的递归
        if (root.left == null && root.right == null) {
            return root;
        }

        //定义一个tmp结点，来为root左右结点交换作中间站
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;

        //递归左右子树
        invertTree(root.left);
        invertTree(root.right);


        return root;
    }

    //对称二叉树
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isSymmetricChild(root.left, root.right);
    }

    public boolean isSymmetricChild(TreeNode leftTree, TreeNode rightTree) {
        //1.结构上
        //1.1左为空右不为空或者左不为空右为空
        if (leftTree == null && rightTree != null || leftTree != null && rightTree == null) {
            return false;
        }
        //1.2左右都为空
        if (leftTree == null && rightTree == null) {
            return true;
        }
        //2.值
        //2.1左右的值都不相同
        if (leftTree.val != rightTree.val) {
            return false;
        }
        //2.2左右的值都相同
        return isSymmetricChild(leftTree.left, rightTree.right) && isSymmetricChild(leftTree.right, rightTree.left);
    }

    //平衡二叉树  O(n)
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        return getHeight2(root) >= 0;
    }

    //我们规定一下如果不是平衡树返回负数，是平衡树返回树的高度
    public int getHeight2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = getHeight2(root.left);
        int rightHeight = getHeight2(root.right);
        if (leftHeight >= 0 && rightHeight >= 0 && Math.abs(leftHeight - rightHeight) <= 1) {
            return Math.max(leftHeight, rightHeight) + 1;
        } else {
            return -1;
        }
    }

    //寻找最近的公共祖先(递归的方式)
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        //1.p或q其中一个为root
        if (p == root || q == root) {
            return root;
        }
        //2.递归左树
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        //3.递归右树
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        //4.判断左右树返回的值是否为空
        //4.1左右两树都不为空，则返回root说明p和q在两侧。
        if (left != null && right != null) {
            return root;
        } else if (left != null) {
            //4.2左树不为空，右树为空，则说明在同一侧，则返回左树即可。
            return left;
        } else {
            //4.3右树不为空，左树为空，则说明在同一侧，则返回右树即可。
            return right;
        }
    }

    //找到指定的结点所路过的路径并存储在栈中的方法
    public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
        if (root == null) {
            return false;
        }
        stack.push(root);
        if (root == node) {
            return true;
        }
        boolean left = getPath(root.left, node, stack);
        if (left) {
            return true;
        }

        boolean right = getPath(root.right, node, stack);
        if (right) {
            return true;
        }
        //说明root的左右两边都为null，弹出这个root.val
        stack.pop();
        return false;
    }

    //通过存储根结点到目标结点的路径上的结点来找到最近的公共祖先
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        /*ArrayDeque;
        LinkedList;*/
        getPath(root, p, stack1);
        getPath(root, q, stack2);

        int size1 = stack1.size();
        int size2 = stack2.size();
        if (size1 > size2) {
            int size = size1 - size2;
            while (size != 0) {
                stack1.pop();
                size--;
            }
        } else {
            int size = size2 - size1;
            while (size != 0) {
                stack2.pop();
                size--;
            }
        }

        while (!stack1.isEmpty() && !stack2.isEmpty()) {
            if (stack1.peek().equals(stack2.peek())) {
                return stack1.pop();
            } else {
                stack1.pop();
                stack2.pop();
            }
        }
        return null;
    }

    //根据二叉树创建字符串
    public String tree2str(TreeNode root) {
        StringBuilder sbu = new StringBuilder();
        tree2strChild(root, sbu);
        return sbu.toString();
    }

    private void tree2strChild(TreeNode root, StringBuilder sbu) {
        if (root == null) {
            return;
        }
        sbu.append(root.val);
        // 递归左树
        if (root.left != null) {
            sbu.append("(");
            tree2strChild(root.left, sbu);
            sbu.append(")");
        } else {
            if (root.right == null) {
                return;
            } else {
                sbu.append("()");
            }
        }
        //递归右树
        if (root.right != null) {
            sbu.append("(");
            tree2strChild(root.right, sbu);
            sbu.append(")");
        }
    }
    //二叉树的前序遍历（非递归）
   /* public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                list.add(cur.val);
                cur = cur.left;
            }
            // 左边为空
            TreeNode top = stack.pop();
            cur = top.right;
        }
        return list;
    }*/
    //二叉树的中序遍历（非递归）
    /*public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            // 左边为空
            TreeNode top = stack.pop();
            list.add(top.val);
            cur = top.right;
        }
        return list;
    }*/

    //二叉树的后序遍历（非递归）
   /* public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) {
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode prev = null;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            if(top.right == null || top.right == prev ) {
                stack.pop();
                list.add(top.val);
                prev = top;
            }else {
                cur = top.right;
            }
        }
        return list;
    }*/

    //返回的第一个指针，即为最小值，先定为null
    TreeNode head = null;
    //中序遍历当前值的上一位，初值为最小值，先定为null
    TreeNode pre = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null)
            //中序递归，叶子为空则返回
            return null;
        //首先递归到最左最小值
        Convert(pRootOfTree.left);
        //找到最小值，初始化head与pre
        if (pre == null) {
            head = pRootOfTree;
            pre = pRootOfTree;
        }
        //当前节点与上一节点建立连接，将pre设置为当前值
        else {
            pre.right = pRootOfTree;
            pRootOfTree.left = pre;
            pre = pRootOfTree;
        }
        Convert(pRootOfTree.right);
        return head;
    }
    //输出二叉树的右视图
    ArrayList<Integer> ret =  new ArrayList<>();
    public List<Integer> rightSideView(TreeNode root) {
        // 1.判断根结点是否为空
        if (root == null) {
            return ret;
        }
        // 2.不空，则将根结点放入队中
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            while(size !=  0) {
                TreeNode tmp = queue.poll();
                if(tmp.left != null) {
                    queue.offer(tmp.left);
                }
                if(tmp.right != null) {
                    queue.offer(tmp.right);
                }
                size--;
                if(size == 0) {
                    ret.add(tmp.val);
                }
            }
        }
        return ret;
    }
    //输出二叉树的左视图
    ArrayList<Integer> leftRet =  new ArrayList<>();
    public List<Integer> leftSideView(TreeNode root) {
        // 1.判断根结点是否为空
        if (root == null) {
            return leftRet;
        }
        // 2.不空，则将根结点放入队中
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int j = 0; j < size; j++) {
                TreeNode tmp = queue.poll();
                if(tmp.left != null) {
                    queue.offer(tmp.left);
                }
                if(tmp.right != null) {
                    queue.offer(tmp.right);
                }
                if(j == 0) {
                    leftRet.add(tmp.val);
                }
            }
        }
        return leftRet;
    }
}


